iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 23
0
自我挑戰組

學習資料結構30天系列 第 23

[Data Structure] - Hash Table

  • 分享至 

  • xImage
  •  

前言

昨天介紹的Balanced Search Tree是為了改善不平衡的Binary Search Tree的搜尋速度。
今天介紹一個搜尋速度很快的資料結構 - Hash Table

Hash

  • 筆者的朋友分享了對Hash的理解:

Hash 是 雜湊
Potato 是 馬鈴薯
Hash Potato 就變成 薯餅了 !

Hash Table

  • 一種儲存 Key-Value pair 的 mapping 關係的資料結構
    Key-Value pair,可以用Array實作,利用Array的index作為key,將value存放進去,但是Array就是需要事先宣告Array大小,Hash table 能解決這個問題。
  • 目標是: Key的數量,就是Table的size -> Table的size= Θ(Key的數量)
  • 透過 Hash function 使得index = function (key),value就存在table 的index裡。
  • 兩筆value存進Table的同一個空格裡,就是發生Collision
    -> 解決方法 :
    1. 找出table有空位的地方,再把value存進去。
    2. 把存在同一個空格的value,用linkedlist連結起來。

上一篇
[Data Structure][Tree] - Balanced Search Tree
下一篇
[Data Structure][Tree] - Red-Black Tree
系列文
學習資料結構30天30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言